package nowcoder;

import java.util.Arrays;

public class GreatestSumOfSubarray {

	public static void main(String[] args) {
		int[] a = {1,2,3,4,5};
		System.out.println(FindGreatestSumOfSubArray2(a));
	}

	public static int FindGreatestSumOfSubArray(int[] array) {

		if(array == null || array.length == 0)
			return 0;

		int l = array.length;
		int max = array[0];
		for(int i = 1; i <= l; i++) {
			int sum = 0;
			for(int j = 0; j <= l - i; j++) {
				if(j == 0) {
					for(int k = 0; k < i; k++) {
						sum += array[j + k];
					}
				}else {
					sum -= array[j - 1];
					sum += array[j + i - 1];
				}

				if(sum > max)
					max = sum;
			}
		}

		return max;
	}

	public static int FindGreatestSumOfSubArray2(int[] array) {

		if(array == null || array.length == 0)
			return 0;

		int l = array.length;

		int[] dp = new int[l];
		dp[0] = array[0];
		
		for(int i = 1; i < l; i++) {
			dp[i] = Math.max(dp[i - 1] + array[i], array[i]);
		}
		
		return Arrays.stream(dp).max().getAsInt();
	}

}
